1. Field of the Invention
The present invention relates to a packet communication system which, when receives unit packets each corresponding to a predetermined amount of data from a plurality of terminals, arranges these packets to once form a packet queue, sequentially selects packets from the packet queue, and sequentially transmits them.
2. Description of the Related Art
An example of systems of transmitting voice data on a packet basis is shown in FIG. 5. The system of FIG. 5 includes multiplex lines 1, packet exchanges 2A, 2B and 2C, packet terminals 3A, 3B and 3C, exchanges 4A, 4B and 4C, and telephone sets 5. In the system, a voice data inputted to, for example, the packet terminal 3A is encoded, divided into predetermined data units, assembled into packets attached with a party destination data and then transmitted to the party packet terminal 3B through the packet exchange 2A and 2B.
Referring next to FIG. 6, there is shown a block diagram of interior arrangement of one of the packet exchanges 2A to 2C, which includes terminal interfaces 2-1 provided as associated with the respective packet terminals, a line interface 2-2 with respect to the multiplex lines 1, a controller 2-3, a bus access controller 2-4, an interrupt control bus 2-5, a control bus 2-6, an access control bus 2-7, and a data bus 2-8. Each of the terminal interfaces 2-1, when receiving a calling packet from the associated packet terminal connected thereto, issues an interrupt command to the controller 2-3 via the interrupt control bus 2-5. The controller 2-3, when confirming the reception of an interrupt command, gets access to a memory (not shown) provided within the terminal interface 2-1 through the control bus 2-6 and confirms the calling data indicative of the party number, window size (the number of packets per unit time transmittable to the party side) and so on. Thereafter, the controller 2-3 outputs to the access control bus 2-7 an access request to the data bus 2-8 to transmit a connection request packet to the opposing node (exchange) of the party packet terminal. After having gotten an access authority, the controller 2-3 transmits the connection request packet to the line interface 2-2 through the data bus 2-8. At this time, the line interface 2-2 itself assembles the connection request packet like the data packet and sends it onto the multiplex line 1. The line interface 2-2, when receiving a connection approval or disable packet from the opposing node, sends the received packet to the controller 2-3. When the controller 2-3 receives, for example, the connection approval packet, the controller causes a connection table to be created in a memory (not shown) provided between the line interface 2-2 and the terminal interface 2-1 and at the same time, the controller sends the connection approval packet to the terminal interface 2-1. The terminal interface 2-1, when receiving the connection approval packet from the controller 2-3, sends the connection approval packet to the associated packet terminal, after which the packet exchange is shifted to its data transfer phase. In this phase, the terminal interface 2-1 sends a data packet to the line interface 2-2 through the data bus 2-8. In this case, the data packet sent to the line interface 2-2 has such a header part H attached to a data part D as shown in FIG. 7 based on the connection table created by the controller 2-3. The line interface 2-2, after storing the received data packet in its buffer, transmits the data packet to the multiplex line 1. The above operation is repeated similarly with respect to the subsequent data packets in the data transfer phase. Even when the controller 2-3 receives the connection disapproval packet (disconnection mode), substantially the same operation holds true for the connection request mode, except that the connection table is deleted.
FIG. 8 shows the interior arrangement of the line interface 2-2 (with arrows directed only to the multiplex line). The illustrated line interface includes a data bus interface 11, an address coincidence checker 12, a packet distributing part 13, a buffer memory BM having a plurality of rows of packet queues 14-1 to 14-n stored therein, a send packet decider 15, and a lien interface 16. The data bus interface 11, which is provided for interface with the data bus 2-8 of FIG. 6, sends or receives packets at the timing of the data bus 2-8. The address coincidence checker 12 decides by comparison whether or not the received packet is destined for its own line interface, so that, when the received packet is destined for its own, the checker 12 transfers the received packet to the packet distribution part 13 and otherwise, the checker 12 discards the packet. The packet distribution part 13 decides on the basis of the information of the header part H of the received packet in which one of the packet queues 14-1 to 14-n the received packet is to be stored. The information of the header part H includes data associated with the connection and priority data on immediateness and discarding rate. The packet distribution part 13 distributes the packet to any one of the packet queues 14-1 to 14-n according to, for example, the priority data of these header data H. The send packet decider 15 is used to determine one of the packet queues 14-1 to 14-n from which a packet is to be extracted. The line interface 16, which forms an interface with the multiplex line 1, sends the extracted packet onto the multiplex line in synchronism with the clock of the line.
Shown in FIG. 9 is the details of the packet distribution part 13 and buffer memory BM in FIG. 8, which includes a packet distributor 6-1, a distribution controller 6-2, a timer CLK, timer buffer memories 7-11 to 7-n1 for sequentially storing therein and outputting a time from the timer CLK in the first-in first-out (FIFO) manner, data buffer memories 7-12 to 7-n2 for sequentially storing therein and outputting a packet in the FIFO manner, staying-packet counters 7-13 to 7-n3 for counting the numbers of packets stored in the data buffer memories, a transmitter 8-1, and a send/discard packet decider 8-2.
More specifically, the packet distributor 6-1 receives a packet from the data bus interface 11 of FIG. 8 and distributingly sends the received packet to any one of the data buffer buffer memories 7-12 to 7-n2. The distribution controller 6-2 identifies the priority data designated by the header part H of the packet received from the data bus interface 11, and instructs the packet distributor 6-1 to distribute the packet to the data buffer memory designated by the priority data. For example, assume that the priority data has classes 1 to n which are associated with the data buffer memories 7-12 to 7-n2 respectively. Then a packet having the priority data of class 1 is sent from the packet distributor 6-1 to the data buffer memory 7-12, a packet having the priority data of class 2 is sent from the packet distributor 6-1 to the data buffer memory 7-22, and similarly a packet having the priority data of class n is sent from the packet distributor 6-1 to the data buffer memory 7-n2.
The data buffer memories 7-12 to 7-n2 sequentially store the respective packets distributed by the packet distributor 6-1, whereby packet queues of the classes 1 to n are formed in the data buffer memories 7-12 to 7-n2 respectively.
Each time a packet is input to the data buffer memory 7-12, the timer buffer memory 7-11 sequentially stores therein a time from the timer CLK. Similarly, each time a packet is input to the data buffer memory 7-n2, the data buffer memory 7-12 sequentially stores therein a time from the timer CLK. As a result, series or rows of times (time rows) are formed in the respective timer buffer memories 7-11 to 7-n1 and correspond to the associated packet queues within the data buffer memories 7-12 to 7-n2. More in detail, for example, the heading times of the time rows in the timer buffer memories 7-11 to 7-n1, that is, the first-input times indicate the input times of the heading packets in the respective packet queues which are located at their heads or are first input.
The transmitter 8-1 sequentially reads out the heading packets from any of the data buffer memories 7-12 to 7-n2 and sequentially transmits the read-out packets. The send/discard packet decider 8-2, when it is in its send control mode, selects one of the heading packets within the data buffer memories 7-12 to 7-n2 to be immediately transmitted, on the basis of the current time received from the timer CLK, the heading times in the respective timer buffer memories 7-11 to 7-n1, and the classes 1 to n of the data buffer memories 7-12 to 7-n2, and the decider 8-2 instructs the transmitter 8-1 to extract the selected heading packet. That is, the transmitter 8-1 extracts the instructed packet from the data buffer memories and transmits it.
Selection of the heading packet done at the send/discard packet decider 8-2 is carried out in accordance with the following expression (1). EQU Max {D1W1, D2W2, . . . , DjWj, . . . , DnWn} (1) EQU 1.ltoreq.j.ltoreq.n
where Dj denotes a time during which the heading packet within the data buffer memory of class j stays therein and which corresponds to a difference between the heading time within the timer buffer memory associated with the data buffer memory, i.e., the input time of the heading packet and the current time. In addition, Wj denotes a weight factor previously given to the class j and satisfies the following relationship. EQU Wj-1&gt;Wj&gt;Wj+1
That is, the respective values D1W1 to DnWn in the expression (1) are found with respect to the respective heading packets within the data buffer memories 7-12 to 7-n2. One of the packets corresponding to the maximum of these values D1W1 to DnWn is selected as a packet to be immediately transmitted and the selected packet is transmitted from the transmitter 8-1. Such operation is sequentially carried out for every packet transmission.
The selection of a packet to be immediately transmitted according to the expression (1) is a directest and proper method to secure the transmission quality. This method, however, must perform subtraction operation to calculate the value Dj, multiplication operation to calculate, and comparison operation to find a maximum among the values D1W1 to DnWn; thus the send packet decider 8-2 must perform a considerable amount of operation 0(3n) for every packet. For this reason, the method has been defective in that the processing ability of the send packet decider 8-2 becomes insufficient, high speed processing is impossible and the upper limit of the class number n is restricted by such conditions. In addition, the method has such a demerit that, although calculators for the subtraction and multiplication may be dispersedly provided for the respective data buffer memories, such an arrangement requires a very large scale of hardware, which results in that it is impossible to realize a simplified arrangement of the same circuit units with difficult system integration and poor applications.
Explanation will next be made as to how the send/discard packet decider 8-2 performs the discarding control. The staying-packet counters 7-13 to 7-n3 count the numbers of packets staying in the respective data buffer memories of classes 1 to n. The number of packets accumulatable in each of the data buffer memories 7-12 to 7-n2 is limited to a specific value in the illustrated example. Thus when the data buffer memory 7-j2 of class j is full of packets, input of a new packet to the data buffer memory 7-j2 causes its overflow. For this reason, in the discarding control, when the number of packets staying in the data buffer memory 7-j2 of class j exceeds a predetermined value, the data buffer memory discards one of the stay packets which has the longest stay time, that is, the heading packet.
The above discarding operation, however, is carried out without discriminating the packet connection, i.e., the transmission route of that packet, thus resulting in that, when packets in the data buffer memory 7-j2 of class j abruptly increase in number, there is a danger that the data buffer memory 7-j2 might continuously discard many packets flowing through the same connection. When many packets flowing through the same connection are continuously discarded in this way, this involves such a problem that the communication quality of the connection is remarkably deteriorated. As one of methods of avoiding this problem, it is considered, when it is desired to discard packets on a connection, to discard the packets only after passage of a predetermined time. In this method, however, the data buffer memory 7-j2 of FIFO type cannot select and discard packets other than the heading packet as mentioned above and any consideration does not lead to paying to the connection.
In this way, the prior art packet communication system has a problem that, when a packet in any one of a plurality of packet queues to be immediately transmitted is to be determined, the send packet decider must perform the subtraction and multiplication for each of the packet queues as well as comparison between products of the subtraction and multiplication, thus making it impossible to realize high-speed calculation processing. For attaining high-speed calculation processing, it is possible to provide a calculating part for each of the packet queues, but such dispersion of calculating parts disables the realization of a simplified arrangement of the same circuit units with difficult integration of the system.
With respect to the packet discarding control, on the other hand, the FIFO type data buffer memory cannot select and discard packets other than the leading packet, which may undesirably result in that the data buffer memory continuously discards many packets flowing through the same connection, in which case the communication quality of the connection is deteriorated to a large extent.